package com.xyhuo.leetcode.december;

import java.util.*;

/**
 * 四数之和
 * https://leetcode.cn/problems/4sum/
 *
 * @time 2023/12/6
 */
public class FourSum {

//    public static void main(String[] args) {
//        FourSum fs = new FourSum();
////        int[] nums = {1, 0, -1, 0, -2, 2};
////        fs.fourSum(nums, 0);
//        int[] nums = {1000000000, 1000000000, 1000000000, 1000000000};
//        fs.fourSum(nums, -294967296);
//        //-2147483648
//        //-294967296
//        // 1000000000
//    }

    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        int length = nums.length;
        Set<String> set = new HashSet<>();
        for (int i = 0; i < length - 3; i++) {
            for (int j = i + 1; j < length - 2; j++) {
                long tmp = target - nums[i];
                tmp -= nums[j];
                int left = j + 1, right = length - 1;
                String tmpNumsStr = nums[i] + "#" + nums[j] + "#";
                while (true) {
                    if (left >= right) {
                        break;
                    }
                    if (nums[left] + nums[right] > tmp) {
                        right--;
                    } else if (nums[left] + nums[right] == tmp) {
                        String numsStr = tmpNumsStr + nums[left] + "#" + nums[right];
                        if (!set.contains(numsStr)) {
                            set.add(numsStr);
                            List<Integer> item = new ArrayList<>();
                            item.add(nums[i]);
                            item.add(nums[j]);
                            item.add(nums[left]);
                            item.add(nums[right]);
                            ans.add(item);
                        }
                        right--;
                    } else {
                        left++;
                    }
                }
            }
        }
        return ans;
    }
}
